package com.cqs.leetcode.dp;

/**
 * @author lixiaowen
 * @create 2019-12-13
 */
public class HouseRobberII213 {

    /**
     * 分为两种情况来解
     * 1. 第一间偷
     * 2. 第一间不偷
     *
     * @param nums
     * @return
     */
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        return Math.max(rob1(nums), rob2(nums));
    }

    /**
     * 第一个房间没有偷 会影响到第二间房间(一定偷)
     *
     * @param nums
     * @return
     */
    private int rob1(int[] nums) {
        int[] result = new int[nums.length];
        //标识第一间不偷
        result[0] = 0;
        //第二间一定偷
        result[1] = nums[1];
        for (int i = 2; i < nums.length; i++) {
            result[i] = Math.max(result[i - 1], nums[i] + result[i - 2]);
        }
        return result[nums.length - 1];
    }

    /**
     * 第一个房间偷了 第二间和最后一间不能偷
     *
     * @param nums
     * @return
     */
    private int rob2(int[] nums) {
        int[] result = new int[nums.length];
        //第一间偷了,第二间一定不能偷
        result[1] = nums[1];
        for (int i = 2; i < nums.length - 1; i++) {
            result[i] = Math.max(result[i - 1], nums[i] + result[i - 2]);
        }
        //最后一个房间不能偷
        return result[nums.length - 1] = result[nums.length - 2];
    }

}
